package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}10:27
 */
public class LeetCode40 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0){
            return res;
        }
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates,target,0,list);
        return res;
    }

    public void dfs(int[] ccandidates,int target,int begin,List<Integer> list){
        if (target == 0){
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = begin; i < ccandidates.length; i++) {
            if (ccandidates[i] > target){
                continue;
            }
            if (i > begin && ccandidates[i] == ccandidates[i - 1]){// 这里是处理重复结果的方法 如果以当前结点为头结点的所有组合都找完了，那么下一个与他他相同的头结点就不用去找了。
                continue;
            }
                target -= ccandidates[i];
                list.add(ccandidates[i]);
                dfs(ccandidates, target, i + 1, list);
                list.remove(list.size() - 1);
                target += ccandidates[i];
        }
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode40().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8).toString());
    }
}
